A recent work of Schmidhuber et al. (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted kXOR problem running quartically faster than all known classical algorithms.

In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant k. Thus for such k, the quantum advantage of Schmidhuber et al. becomes only quadratic.

Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.

Joint work with Meghal Gupta, William He, and Ryan O'Donnell.